The open shop scheduling problem (OSSP) is a scheduling problem where, given n jobs and m workstations, each job has to visit a workstation at least once. The order in which this happens is not relevant (in contrast to the job-shop problem, where the order of jobs does matter).
The OSSP can be solved in polynomial time for two machines. For three or more machines, the problem is known to be NP-hard. However, when all tasks have the same length, the problem may be solved in polynomial time as an instance of the edge coloring problem for bipartite graphs.